5.2.1.1. Aritmetik Ortalama için T(n) Hesabı

Örnek: Aşağıda, bir dizinin aritmetik ortalamasını bulan ve sonucu çağırana gönderen bulOrtalama() adlı fonksiyonun kodu verilmiştir. Bu fonksiyonun yürütme zamanını gösteren T(n) bağıntısı ayrık C dili deyimlerine göre belirleyiniz.

	float bulOrta(float A[], int n)
	{
	float ortalama, toplam=0;
	int k;

	for(k=0; k<n; k++)
	toplam+=A[k];
	ortalama=toplam/n;
	return ortalama;
	}

Çözüm: Programdaki ayrık C dili deyimleri numaralandırılmış satırlardaki k=0, k<n, toplam+=A[k] gibi atama, karşılaştırma ve aritmetik işlemlerdir. Buna göre, ve . satırlarda birer işlem yapılmaktadır. Dolayısıyla bu iki satırın etkisi 2'dir. . satırda ise 1 işlem yapılmaktadır; ancak, bir döngü içerisinde olduğu için yapılan toplam işlem sayısı 1*çevrimsayısı'ndan hesaplanır. . satıra bakılırsa n çevrimlik bir döngü vardır ve dolayısıyla . satırdaki toplama işlemi n kez yapılır. Bu durumda toplam işlem sayısı, şimdilik , ve . satırlardan toplam işlem sayısı n+2 'dir. Ancak bir de for deyim içerisindeki k=0, k<n ve k++ işlemleri vardır; k=0 işlemi bir kez, k<n işlemi n+1 kez ve k++ işlemi n kez yapılır. Dolayısıyla toplam işlem sayısını gösteren T(n), tüm satırlardaki işlem sayılarının toplamından bulunur.

. satırda
1+(n+1)+n= 2n+2

. satırda
n

. satırda
1

. satırda
1

T(n) = (2n+2)+(n)+1+1 = 3n+4

olarak bulunur.

Yukarıda yapılan hesaplamaların daha kolay görülebilmesi için tablo yöntemi kullanılabilir. Örneğin aşağıda aynı hesaplama tablo yöntemiyle yapılmıştır:

Temel Hesab Birimi İşlem Tekrarı Toplam

float bulOrta(float A[], int n) - - -

{ - - -

   float ortalama, toplam=0; - - -

   int k; - - -

   for(k=0; k<n; k++) 1,1,1 1, (n+1), n (2n+2)

       toplam+=A[k]; 1 n n

   ortalama=toplam/n; 1 1 1

   return ortalama; 1 1 1

} - - -

T(n)=3n+4